/*
 * One example for NOI CSP-J Lesson 10:
 * <https://courses.fmsoft.cn/plzs/noijunior-csp-exercises-lower.html>
 *
 * Author: Vincent Wei
 *  - <https://github.com/VincentWei>
 *  - <https://gitee.com/vincentwei7>
 *
 * Copyright (C) 2025 FMSoft <https://www.fmsoft.cn>.
 * License: GPLv3
 */
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <cassert>

using namespace std;

using llong_t = long long;
using adj_list = vector<vector<pair<llong_t, int>>>;

int dijkstra(adj_list& graph, int k, int from)
{
    int V = graph.size();

    // 创建一个优先队列，存储用于对比的顶点。
    priority_queue<pair<llong_t, int>, vector<pair<llong_t, int>>, greater<pair<llong_t, int>>> pq;

    // 针对 k 的不同取值，创建从 from 到其他顶点的距离的矢量，
    // 并初始化为无限大（LLONG_MAX)
    vector<vector<llong_t>> dist(V, vector<llong_t>(k+1, LLONG_MAX));

    // 针对 k 的可能取值，维护已访问数组；初始化为 false。
    vector<vector<bool>> visited(V, vector<bool>(k+1));

    // 将 from 放入优先队列，并将其距离初始化为 0。
    pq.push({0, from});
    dist[from][0] = 0;

    // 循环处理直到优先队列为空。
    while (!pq.empty()){

        llong_t t_arrive = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (visited[u][t_arrive%k]) {
            continue;
        }
        visited[u][t_arrive%k] = true;

        for (auto x : graph[u]){

            int v = x.first;
            int a = x.second;
            llong_t t;

            if (t_arrive >= a) {
                t = t_arrive;
            }
            else {
                t = ((a - t_arrive + k - 1)/k) * k + t_arrive;
            }

            if (dist[v][(t+1)%k] > t+1) {
                dist[v][(t+1)%k] = t+1;
                pq.push({t+1, v});
            }
        }
    }

    if (!visited[V-1][0])
        return -1;

    return dist[V-1][0];
}

int main()
{
    adj_list graph(5 + 1);
    graph[1].push_back({2, 0});
    graph[2].push_back({5, 1});
    graph[1].push_back({3, 0});
    graph[3].push_back({4, 3});
    graph[4].push_back({5, 1});

    int ans;
    ans = dijkstra(graph, 3, 1);
    clog << ans << endl;
    assert(ans == 6);

    int n, m, k;
    cin >> n >> m >> k;
    adj_list graph2(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, a;
        cin >> u >> v >> a;
        graph2[u].push_back({v, a});
    }

    ans = dijkstra(graph2, k, 1);
    cout << ans << endl;
    return 0;
}

